package heap;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class leetcode347前K个高频元素 {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (Integer integer : map.keySet()) {
            if (queue.size() == k) {
                if (map.get(integer) > queue.peek()[1]) {
                    queue.poll();
                    queue.offer(new int[]{integer,map.get(integer)});
                }
            } else {
                queue.offer(new int[]{integer,map.get(integer)});
            }
        }
        int size = queue.size();
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = queue.poll()[0];
        }
        return result;
    }
}
